package algorithms.sort;

/**
 * 先下沉后上浮
 * HeapSort在下沉排序期间先exch(),后sink()，大多数重新插入堆的元素会直接沉入堆底
 * Floyd发现，可以通过免去检查元素是否到达正确位置来节省时间。
 * 具体是，在下沉中直接提升较大的子节点直至堆底，然后再使元素上浮至正确位置
 * 这个想法几乎可以将比较减少一半
 * 
 * @author glogo
 *
 */
public class HeapSort2 {

	public static void sort(Comparable[] a){
		int N = a.length;
		
		for(int k = N/2; k >= 1; k--)	sink(a, k, N);
		
		
		
	}

	
	private static void sink(Comparable[] a, int k, int N){
		while(2*k <= N){
			int j = 2*k;
			if(j < N && less(a[j], a[j+1])) j++;
			if(!less(a[k], a[j])) break;
			exch(a, k, j);
			k = j;
		}
		
	}
	
	
	private static boolean less(Comparable v, Comparable w){
		return v.compareTo(w) < 0;
	}
	
	private static void exch(Comparable[] a, int i, int j){
		Comparable t = a[i];
		a[i] = a[j];
		a[j] = t;
	}
}
